 function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 
function Convert(pRootOfTree)
{
    // write code here
    if(pRootOfTree === null) return null // 如果是一个空树的话返回空节点
    // 设置两个节点 分别叫做head 和tail 用来标记已经转化好的双向链表的头部和尾部
    var head = null
    var tail =  null
    // 定义一个递归函数 需要的参数是当前的节点 也就是需要完成递归的这个树的根节点
    function convert(cur){
      if(cur === null) {
        return // 如果当前的节点是null的那我们直接返回 因为不需要做任何事
      }
      // 否则的话 我们先转化他的左子树
      convert(cur.left)
      // 接下来判断一下 如果说这个尾部的节点是null的 也就是说还没有进行转换
      if(tail === null){ // 还没有进行转换
        // 那么我们当前的这个节点其实就是那个要返回的双向链表的头结点 我们把这个赋给head
        head = cur
      }else{
        // 否则的话 我们把当前的节点和已经转化好的链表进行连接
        // 让链表的尾结点的右指针指向当前的节点
        tail.right = cur
      }
      // 让当前节点的左指针指向尾结点
      cur.left = tail
      // 并且将当前节点赋给用来标记链表的tail
      tail = cur
      // 完成上一步之后 我们再转换右子树
      convert(cur.right)
    }
    // 在主函数中调用递归函数 这样就把它给转换好了
    convert(pRootOfTree)
    // 但是题目要求是循环双向的 还需要重复设置一下这个条件
    // 也就是让头结点的左指针指向尾结点 尾结点的右指针指向头结点
    // var newHead = head
    // var newTail = tail
    // newHead.left = newTail
    // newTail.right = newHead
    return head // 最后返回头结点 还需要判断他给的是一个空的情况
}
module.exports = {
    Convert : Convert
};